#include<bits/stdc++.h>
using namespace std;
/*class Solution {
public:
    string longestWord(vector<string>& words) {
        unordered_set<string> hash={""};
        string ret="";
        sort(words.begin(),words.end(),[](const string& a,const string& b)
        {return a.size()!=b.size()?a.size()<b.size():a<b;});
        for(const string& s:words)
        {
            if(hash.count(s.substr(0,s.size()-1)))
           { 
            hash.insert(s);
            if(s.size()>ret.size()||(ret.size()==s.size()&&s<ret)) 
            { 
                
                ret=s;
            }
            }
        }
        return ret;

    }
};*/

class trie
{
    private:
    vector<trie*> children;
    bool flag;
    public:
    trie()
    {
        children=vector<trie*>(26);
        flag=true;
    }
    void insert(const string& s)
    {
        trie* cur=this;
        for(char ch:s)
        {
            int k=ch-'a';
            if(cur->children[k]==nullptr) cur->children[k]=new trie();
            cur=cur->children[k];
        }
        cur->flag=true;
    }
    bool search(const string& s)
    {
        trie* cur=this;
        for(char ch:s)
        {
            int k=ch-'a';
            if(cur->children[k]==nullptr||cur->flag!=true) return false;
            cur=cur->children[k];
        }
        return cur!=nullptr&&cur->flag;
    }
};
class Solution {
public:
    string longestWord(vector<string>& words) {
        string ret="";
        trie* root=new trie();
        trie* cur=root;
        for(const string& s:words) cur->insert(s);
        for(const string& s:words)
        {
            if(cur->search(s))
            {
                if(s.size()>ret.size()||(s.size()==ret.size()&&s<ret)) ret=s;
            }
        }
        return ret;
    }
};